1. Field of Invention
The invention relates to a data encoding method and device for compressing a multiple-valued information source, and a data decoding method and device for decompressing (decoding) a compressed multiple-valued information source. Specifically, it relates to a method and device for converting a multiple-valued information source into a binary bit series and compressing that binary bit series or coding that binary bit series.
2. Description of Related Art
Conventionally, arithmetic encoding methods which handle binary information consisting of "0"s and "1"s are known in the world of information theory. The conventional arithmetic encoding method is an entropy encoding method and it has the property of being intrinsically reversible (lossless). Also, the principle behind this method has been incorporated into an ideal encoding method for memoryless information sources known as Elias encoding. Specifically, in arithmetic encoding, the corresponding segments of "0"s and "1"s are divided into unequal lengths corresponding to the probability of each symbol occurring, and a target symbol series is assigned to each partial segment. The coordinates of the points included within the segment obtained by recursive iteration of division are encoded as represented by binary points capable of being divided into at least another segment.
In the arithmetic encoding method, as compared with block encoding, which makes specific code words correspond to information source symbols having finite items, the specification of the encoder has advantages such as utilizing minimal memory and hardware capable of high-efficiency and suitable encoding. Through these advantages, this arithmetic encoding method can compress information to a level nearest to the entropy of the information. In the field of information theory and handling of binary signals, this is considered the best and most efficient encoding method. Moreover, this arithmetic encoding method is particularly suitable for encoding Markov information sources.
The following conventional arithmetic encoding methods have been proposed: a Q coder, an arithmetic-type MEL coder, a mini-max coder and an arithmetic coder of multi-value. Also known conventionally is an improvement of these arithmetic encoding methods referred to as a QM encoder. The QM coder is commonly used in the following two standards: the color still picture encoding standard (JPEG); and the binary image encoding standard (JBIG). This encoder is used in encoding binary information sources, and when encoding a multiple-valued information source such as in JPEG, preprocessing is necessary for converting the multiple-valued information source into binary. In this case, the number of binary symbols to be encoded increases, but it becomes possible to convert to a binary series without increasing the amount of information asia multiple-valued information source.
The design of the QM coder is explained in detail in the regulations of JPEG and JBIG. However, for comparison with the present invention, which is described in detail later, a schematic of the QM coder is explained below and shown in FIG. 18. Because the configuration of an arithmetic-type entropy decoder is substantially identical to the configuration of an entropy decoder, its explanation is omitted here.
The QM coder 101, which serves as the arithmetic-type entropy encoder, is configured to include an arithmetic calculator 102 and an occurrence probability generating mechanism 103 to function as a status register. A state parameter table is written within the occurrence probability generating mechanism 103, which is required for determining the occurrence probabilities of the symbols required for encoding. The above-mentioned state parameters are specified by input status signals 106. Also, with regard to the status parameter table specified by the status signals 106, the arithmetic calculator 102 outputs data during the update of calculated parameters as a readout address, and data of the occurrence probability generating mechanism 103, specified by the readout address, is output to the arithmetic calculator 102. The arithmetic calculator 102 compresses input data 104 based on data input in this manner, encodes it and outputs it. Moreover, the status signals 106 are input into the occurrence probability generating mechanism 103. This is, for example, reference pixel data sought by a mechanism such as that referred to as a Markov model, and it is a signal used when raising the compression rate.
The operation of a QM coder configured in this manner is explained based on the flow chart of FIG. 19. First, a value 0xFFFF is assigned to register A in the QM coder 101 and a value 0.times.0000 is assigned to register C. Also, an index ST is initialized for estimating probability (step S100). Next, a coding target symbol (1 bit) is input (step S101). Also, the acquired symbol is determined to be a superior symbol or an inferior symbol (step S102). When it is a superior symbol, the process advances to step S103, and when it is an inferior symbol, the process advances to step S106.
The occurrence probability of an inferior symbol is obtained by referring to a probability estimate table LSZ according to the index ST. Furthermore, the occurrence probability of the superior symbol is obtained by subtracting that from register A and assigning that value to register A (step S103). Subsequently, it is checked as to whether the highest bit of register A is "1" (step S104). If it is "1", the process advances to step S105, and if it is "0", the process advances to step S114. Also, when it is "1", the index ST for encoding the next symbol is obtained by referring to a probability estimate table NMPS according to the index ST (step S105).
In step S102, when it is an inferior symbol, the occurrence probability of the inferior symbol can be obtained by referring to the probability estimate table LSZ according to the index ST, and the value of this occurrence probability is assigned to register A (step S106). Subsequently, the value of register A is added to register C (step S107). Also, by referring to the probability estimate table SWITCH, according to the index ST (step S108), when this is a "1", the process advances to step S109, and the superior symbol is updated.
However, in step S110, index ST is sought for encoding the next symbol by referring to the probability estimate table NLPS according to the index ST. Also, in step S111, both register A and register C shift one bit to the left. Due to this left shift, the highest bit that has overflowed from register C is output as a code word (step S112). Also, in step S113, it is checked as to whether the highest bit of register A is "1". When it is a "1", the process returns to step S111 and repeats the left shift. When the highest bit is "0", the process advances to step S114, and the process ends if the encoded symbol is the final symbol. If it is not, the process returns to step Through this method, the QM coder compresses and encodes the binary bit series being input by using the probability estimate tables LSZ, NMPS, and NLPS.